package cn.njupt.map;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class HashMap<K, V> implements Map<K, V> {

    private int size;

    public static final boolean RED = true;
    public static final boolean BLACK = false;
    public static final float DEFAULT_LOAD_FACTOR=0.75f;

    private Node<K, V>[] tables;

    public static final int DEFAULT_CAPACITY = 1 << 4;

    public HashMap() {
        this(DEFAULT_CAPACITY);
    }

    public HashMap(int capacity) {
        tables = new Node[capacity];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        size = 0;
        for (int i = 0; i < tables.length; i++) {
            tables[i] = null;
        }
    }

    @Override
    public V put(K key, V value) {
        resize();
        int index = index(key);
        Node<K, V> root = tables[index];
        if (root == null) {
            root = createNode(key, value, null);
            tables[index] = root;
            size++;
            afterPut(root);
            return null;
        }
        //哈希冲突怎么办
        Node<K, V> cur = root;
        Node<K, V> parent = null;
        Node<K,V> result=null;
        K k1=key;
        int h1=hash(k1);
        int cmp = 0;
        boolean searched=false;
        while (cur != null) {
            parent = cur;
            K k2=cur.key;
            int h2=cur.hash;
            if(h1>h2){
                cmp=1;
            }else if(h1<h2){
                cmp=-1;
            }else if(Objects.equals(k1,k2)){  //说明相等
                cmp=0;
            }else if(k1!=null && k2!=null
                    && k1.getClass()==k2.getClass()
                    && k1 instanceof Comparable
                    && (cmp=((Comparable)k1).compareTo(k2))!=0){ //如果==0就会进行扫描
//                cmp=((Comparable)k1).compareTo(k2);
            }else if(searched){
                cmp=System.identityHashCode(k1)-System.identityHashCode(k2);
            }else{
                if(cur.left!=null && (result=node(cur.left,k1))!=null
                        ||cur.right!=null && (result=node(cur.right,k1))!=null){
                    cur=result;
                    cmp=0;
                }else {  //代表没有找到
                    searched=true;
                    cmp=System.identityHashCode(k1)-System.identityHashCode(k2);

                }
            }

            if (cmp > 0) {
                //说明在右子树
                cur = cur.right;
            } else if (cmp < 0) {
                //说明在左子树
                cur = cur.left;
            } else {
                //相等
                V oldValue = cur.value;
                cur.value = value;
                cur.key = key;
                return oldValue;
            }
        }
        Node<K, V> newNode = createNode(key,value,parent);
        if (cmp > 0) {
            //右子树
            parent.right = newNode;
        } else {
            //左子树
            parent.left = newNode;
        }
        afterPut(newNode);
        size++;
        return null;

    }
    protected Node<K,V> createNode(K key,V value,Node<K,V> parent){
        return new Node<>(key,value,parent);
    }
    private void resize(){
        if(size/ tables.length<=DEFAULT_LOAD_FACTOR)return;
        //进行扩容
        Node<K,V>[] oldTables=tables;
        tables=new Node[(oldTables.length<<1)];
        Queue<Node<K,V>> queue=new LinkedList<>();
        for (int i = 0; i < oldTables.length; i++) {
            if(oldTables[i]==null)continue;
            queue.offer(oldTables[i]);
            while (!queue.isEmpty()){
                Node<K,V> curNode=queue.poll();
                if(curNode.left!=null){
                    queue.offer(curNode.left);
                }
                if(curNode.right!=null){
                    queue.offer(curNode.right);
                }
                moveNewTable(curNode);
            }
        }
    }

    /**
     * 扩容操作
     * @param node
     */
    private void moveNewTable(Node<K,V> node) {
        node.left=null;
        node.right=null;
        node.parent=null;
        node.color=RED;
        int index=index(node);

        Node<K,V> root=tables[index];
        if(root==null){
            tables[index]=node;
            afterPut(node);
            return;
        }
        Node<K, V> cur = root;
        Node<K, V> parent = null;
        K k1=node.key;
        int h1=node.hash;
        int cmp = 0;
        while (cur != null) {
            parent = cur;
            K k2=cur.key;
            int h2=cur.hash;
            if(h1>h2){
                cmp=1;
            }else if(h1<h2){
                cmp=-1;
            }else if(k1!=null && k2!=null
                    && k1.getClass()==k2.getClass()
                    && k1 instanceof Comparable
                    && (cmp=((Comparable)k1).compareTo(k2))!=0){ //如果==0就会进行扫描
//                cmp=((Comparable)k1).compareTo(k2);
            }else{
                cmp=System.identityHashCode(k1)-System.identityHashCode(k2);
            }

            if (cmp > 0) {
                //说明在右子树
                cur = cur.right;
            } else {
                //说明在左子树
                cur = cur.left;
            }
        }
        node.parent=parent;
        if (cmp > 0) {
            //右子树
            parent.right = node;
        } else {
            //左子树
            parent.left = node;
        }
        afterPut(node);

    }

    /**
     *
     * @param k1 红黑树中的节点
     * @param k2 需要添加进来的节点
     * @return
     */
    public int compare(K k1, K k2,int h1,int h2) {
        //利用hash值进行比较
        int result=h1-h2;
        //hash值不同肯定不是一份对象
        if(result!=0)return result;
        //hash值相同，即result为0，看他们的变量是否相等
        if(Objects.equals(k1,k2))return 0;
        if(k1!=null&& k2!=null){
            //类型不同
            if(k1.getClass()!=k2.getClass()){
                String k1ClassName=k1.getClass().getName();
                String k2ClassName=k2.getClass().getName();
                return k1ClassName.compareTo(k2ClassName);
            }
            //类型相同并且都属于Comparable
            if(k1 instanceof Comparable){
                return ((Comparable)k1).compareTo(k2);
            }
        }
        //类型相同不属于Comparable的子类
        return System.identityHashCode(k1)-System.identityHashCode(k2);
    }

    @Override
    public V get(K key) {
        Node<K,V> node=node(key);
        return node==null?null:node.value;

    }

    public Node<K,V> node(K key){
        Node<K,V> root=tables[index(key)];
        return root==null?null:node(root,key);
    }

    public Node<K,V> node1(K key){
        int index = index(key);
        Node<K, V> cur = tables[index];

        int h=key==null?0:key.hashCode();
        int cmp = 0;
        while (cur != null) {
            cmp = compare(cur.key, key,cur.hash,h);
            if (cmp > 0) {
                //说明在左子树
                cur = cur.left;
            } else if (cmp < 0) {
                //说明在右子树
                cur = cur.right;
            } else {
                //相等
               return cur;
            }
        }
        return null;
    }

    /**
     * 查找node节点以及node节点的左右子树是否包含k1
     * @param k1 传递进来的key
     * @return
     */
    public Node<K,V> node(Node<K,V> cur,K k1){
        //h1代表传递进来的key
        int h1=hash(k1);
        int cmp = 0;
        Node<K,V> result=null;
        while (cur != null) {
            int h2=cur.hash;
            K k2=cur.key;
            if(h1>h2){
                cur=cur.right;
            }else if(h1<h2){
                cur=cur.left;
            }else if(Objects.equals(k1,k2)){
                return cur;
            }else if(k1!=null && k2!=null
                    && k1.getClass()==k2.getClass()
                    && k1 instanceof Comparable
                    && (cmp=((Comparable) k1).compareTo(k2))!=0){ //hash值相同并且类型相同并且具备可比较性
//                如果cmp==0,我们就进行扫描
                if(cmp>0){
                    cur=cur.right;
                }else{
                    cur=cur.left;
                }
            }else if(cur.left!=null && (result=node(cur.left,k1))!=null) { //hash值相同并且不具备可比较性,需要扫描
                return result;
            }else{
                cur=cur.right;//优化一下，代替下面的递归
            }
//            }else if(cur.right!=null && (result=node(cur.right,k1))!=null){
//                return result;
//            }else{
//                return null;
//            }
        }
        return null;
    }

    @Override
    public V remove(K key) {
        return remove(node(key));
    }

    @Override
    public boolean containsKey(K key) {
        return node(key)!=null;
    }

    public V remove(Node<K,V> node){
        Node<K,V> willNode=node;
        if(node==null)return null;
        V oldValue=node.value;

        if(node.hasTwoChildren()){
            //拿到后继节点进行替换
           Node<K,V> replacement=getSuccessor(node);
            node.hash=replacement.hash;
            node.key=replacement.key;
            node.value=replacement.value;
            //将node指向replacement,后期只要删除node即可
            node=replacement;
        }
       Node<K,V> replacement=node.left==null?node.right:node.left;
        if(replacement!=null){
            //度为1
            if(node.parent==null){
                //根节点
                tables[index(node)]=replacement;
                tables[index(node)].parent=null;
            }else if(node.parent.left==node){
                //被删除节点相对于根节点是左子树
                node.parent.left=replacement;
                replacement.parent=node.parent;
            }else{
                //被删除节点相对于根节点是右子树
                node.parent.right=replacement;
                replacement.parent=node.parent;
            }
            fixAfterRemove(replacement);
        }else if(node.parent==null){
            //==null说明是叶子节点
            tables[index(node)] = null;
        }else{
            if(node.parent.left==node){
                //左子树
                node.parent.left=null;
            }else{
                node.parent.right=null;
            }
            fixAfterRemove(node);
        }
        afterRemove(willNode,node);
        size--;
        return oldValue;
    }

    protected void afterRemove(Node<K,V> willNode,Node<K,V> removeNode) {
    }


    public void fixAfterRemove(Node<K,V> node) {
        //下面删除的黑色节点，并且黑色节点不是叶子节点
        if(isRed(node)){
            colorBlack(node);
            return;
        }

        Node<K,V> parent=node.parent;
        if(parent==null){
            return;
        }

        //下面删除的是黑色叶子节点
        boolean left=parent.left==null || node.isLeftChild();
        if(left){
            //被删除的节点相当于父节点的左边
            Node<K,V> brother=parent.right;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateLeft(parent);
                brother=parent.right;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    fixAfterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.right)){
                    rotateRight(brother);
                    brother=parent.right;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.right);
                rotateLeft(parent);
            }
        }else{
            //被删除的节点相当于父节点的右边
            Node<K,V> brother=parent.left;
            if(isRed(brother)){
                colorBlack(brother);
                colorRed(parent);
                rotateRight(parent);
                brother=parent.left;
            }
            if(isBlack(brother.left) &&  isBlack(brother.right)){
                //兄弟节点是一个黑色节点，并且黑色节点没有红色子节点
                boolean parentBlack=isBlack(parent);
                colorRed(brother);
                colorBlack(parent);
                if(parentBlack){
                    fixAfterRemove(parent);
                }

            }else{
                //兄弟节点是一个黑色节点，并且黑色节点有红色子节点
                if(isBlack(brother.left)){
                    rotateLeft(brother);
                    brother=parent.left;
                }
                color(brother,colorOf(parent));
                colorBlack(parent);
                colorBlack(brother.left);
                rotateRight(parent);
            }
        }
    }

    /**
     * 得到node的后继节点
     * @param node 传递的当前节点
     * @return
     */
    public Node<K,V> getSuccessor(Node<K,V> node){
        if(node==null) return node;
        if(node.right!=null){
            return getLeftNode(node.right);
        }else{
            Node<K,V> parent=node.parent;
            while(parent!=null && parent.left!=node){
                node=parent;
                parent=node.parent;
            }
            return parent;
        }
    }

    public Node<K,V> getLeftNode(Node<K,V> node){
        while (node.left!=null){
            node=node.left;
        }
        return node;
    }

    @Override
    public boolean containsValue(V value) {
        if(size==0)return false;
        Queue<Node<K,V>> queue=new LinkedList<>();
        for (int i = 0; i <tables.length ; i++) {
            Node<K,V> node=tables[i];
            if(node==null)continue;
            queue.offer(node);
            while(!queue.isEmpty()){
                Node<K,V> cur=queue.poll();
                if(Objects.equals(cur.value,value)){
                    return true;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if(size==0 || visitor==null)return ;
        Queue<Node<K,V>> queue=new LinkedList<>();
        for (int i = 0; i <tables.length ; i++) {
            Node<K,V> node=tables[i];
            if(node==null)continue;
            queue.offer(node);
            while(!queue.isEmpty()){
                Node<K,V> cur=queue.poll();
                if(visitor.visitor(cur.key,cur.value)){
                    return;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }

        }

    }

    public int index(K key) {
        int index = hash(key) & (tables.length - 1);
        return index;
    }

    public int hash(K key){
        if(key==null) return 0;
        int hash = key.hashCode();
        hash = hash ^ (hash >>> 16);
        return hash;
    }

    public int index(Node<K,V> node){
        return (node.hash)&(tables.length-1);
    }

    protected static class Node<K, V> {
        int hash;
        K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;
        boolean color = RED;


        public Node(K key, V value, Node<K, V> parent) {
            int hash=key==null?0:key.hashCode();
            //扰动计算
            this.hash = hash ^ (hash >>> 16);
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        public boolean isRightChild() {
            return parent != null && parent.right == this;
        }

        public Node<K, V> brother() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }

    public void afterPut(Node<K, V> child) {
        Node<K, V> parent = child.parent;
        if (parent == null) {
            colorBlack(child);
            return;
        }
        if (isBlack(parent)) return;
        Node<K, V> grand = parent.parent;
        Node<K, V> uncle = parent.brother();

        if (isRed(uncle)) {
            //叔父节点是红色
            colorBlack(parent);
            colorBlack(uncle);
            colorRed(parent.parent);
            afterPut(parent.parent);
            return;
        }
        //叔父节点不是红色，就要分情况进行LL,LR,RR,RL
        if (parent.isLeftChild()) {
            //L
            if (child.isLeftChild()) {
//                LL
                colorBlack(parent);
                colorRed(grand);
                rotateRight(grand);
            } else {
                //LR
                colorBlack(child);
                colorRed(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {
            if (child.isRightChild()) {
//                RR
                colorRed(grand);
                colorBlack(parent);
                rotateLeft(grand);
            } else {
//                RL
                colorBlack(child);
                colorRed(grand);
                rotateRight(parent);
                rotateLeft(grand);
            }
        }
    }

    //判断是否是红色节点
    public boolean isRed(Node<K, V> node) {
        return node == null ? false : node.color == RED;
    }

    //判断是否是黑色节点
    public boolean isBlack(Node<K, V> node) {
        return node == null ? true : node.color == BLACK;
    }

    public Node<K, V> color(Node<K, V> node, boolean color) {
        if (node == null) return node;
        node.color = color;
        return node;
    }

    public boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : node.color;
    }

    //染成红色
    public void colorRed(Node<K, V> node) {
        color(node, RED);
    }

    //染成黑色
    public void colorBlack(Node<K, V> node) {
        color(node, BLACK);
    }

    /**
     * 左旋转
     *
     * @param grand 传递的最低不平衡的那个节点
     */
    public void rotateLeft(Node<K, V> grand) {
        Node<K, V> parent = grand.right;
        Node<K, V> child = parent.left;

        grand.right = child;

        parent.left = grand;

        afterRotate(grand, parent, child);
    }

    protected void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
        if (grand.parent == null) {
            tables[index(grand)] = parent;
        } else if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else {
            grand.parent.right = parent;
        }
        parent.parent = grand.parent;
        grand.parent = parent;
        //child可能为null
        if (child != null) {
            child.parent = grand;
        }
    }

    /**
     * 右旋转
     *
     * @param grand 传递的最低不平衡的那个节点
     */
    public void rotateRight(Node<K, V> grand) {
        Node<K, V> parent = grand.left;
        Node<K, V> child = parent.right;

        grand.left = child;

        parent.right = grand;
        afterRotate(grand, parent, child);
    }
}
